#include <hashmap.h>
#include <string.h>
#include <stdlib.h>
#include <symstr.h>
#include <stdio.h>

Hashmap_t hashmap_init(){
    return NULL;
}

static inline uint64_t max(uint64_t x, uint64_t y){
    return x > y ? x : y;
}
static inline void pushup(Hashmap_t node){
    node->dep = max(node->ls->dep, node->rs->dep) + 1;
}
static inline Hashmap_t rotate_left(Hashmap_t node){
    Hashmap_t tmp;
    if(node == NULL) return NULL;
    tmp = node->rs;
    if(tmp == NULL) return node;
    node->rs = tmp->ls;
    tmp->ls = node;
    pushup(node);
    pushup(tmp);
    return tmp;
}
static inline Hashmap_t rotate_right(Hashmap_t node){
    Hashmap_t tmp;
    if(node == NULL) return NULL;
    tmp = node->ls;
    if(tmp == NULL) return node;
    node->ls = tmp->rs;
    tmp->rs = node;
    pushup(node);
    pushup(tmp);
    return tmp;
}
static inline Hashmap_t balance(Hashmap_t node){
    if(node == NULL) return NULL;
    if(node->ls == NULL){
        if(node->rs == NULL)
            node->dep = 1;
        else if(node->rs->dep > 1)
            node = rotate_left(node);
    } else if(node->rs == NULL){
        if(node->ls->dep > 1)
            node = rotate_right(node);
    } else if(node->ls->dep > node->rs->dep + 1) {
        if(node->ls->ls->dep < node->ls->rs->dep)
            node->ls = rotate_left(node->ls);
        node = rotate_right(node);
    } else if(node->ls->dep + 1 < node->rs->dep) {
        if(node->rs->ls->dep > node->rs->rs->dep)
            node->rs = rotate_right(node->rs);
    }
    return node;
}
static Hashmap_t insert(Hashmap_t node, const char *key, uint64_t key0, uint64_t key1, void *value){
    if(node == NULL){
        node = (Hashmap_t)malloc(sizeof(Hashnode_t)+strlen(key)+1);
        node->key0 = key0;
        node->key1 = key1;
        node->value = value;
        node->ls = node->rs = NULL;
        node->dep = 1;
        node->key_str = (char *)(node+1);
        strcpy(node->key_str, key);
    } else {
        if(key0 < node->key0)
            node->ls = insert(node->ls, key, key0, key1, value);
        else if(key0 > node->key0)
            node->rs = insert(node->rs, key, key0, key1, value);
        else if(key1 < node->key1)
            node->ls = insert(node->ls, key, key0, key1, value);
        else if(key1 > node->key1)
            node->rs = insert(node->rs, key, key0, key1, value);
        else{
            int compare = strcmp(node->key_str, key);
            if(compare < 0)
                node->ls = insert(node->ls, key, key0, key1, value);
            else if(compare > 0)
                node->rs = insert(node->rs, key, key0, key1, value);
            else{
                if(node->value != NULL)
                    free(node->value);
                node->value = value;
            }
        }
    }
    return balance(node);
}
Hashmap_t hashmap_insert(Hashmap_t map, const char *key, void *value){
    uint64_t key0, key1;
    strhsh_2(key, &key0, &key1);
    return insert(map, key, key0, key1, value);
}
Hashmap_t hashmap_find(Hashmap_t map, const char *key){
    uint64_t key0, key1;
    strhsh_2(key, &key0, &key1);
    while(map != NULL){
        if(key0 < map->key0)
            map = map->ls;
        else if(key0 > map->key0)
            map = map->rs;
        else if(key1 < map->key1)
            map = map->ls;
        else if(key1 > map->key1)
            map = map->rs;
        else{
            int compare = strcmp(map->key_str, key);
            if(compare < 0)
                map = map->ls;
            else if(compare > 0)
                map = map->rs;
            else
                return map;
        }
    }
    return NULL;
}
Hashmap_t hashmap_free(Hashmap_t map){
    if(map == NULL) return NULL;
    map->ls = hashmap_free(map->ls);
    map->rs = hashmap_free(map->rs);
    if(map->value != NULL)
        free(map->value);
    free(map);
    return NULL;
}